/**
 * https://leetcode.cn/submissions/detail/572474025/
 * 2925. 在树上执行操作以后得到的最大分数
 * Medium, 黄伟杰 2024.10.14
 * 树形DP 对每个节点选或不选进行状态转移
 */

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    long long dfs(int x, int fa, vector<vector<int>> &g, vector<int> &values)
    {
        if (g[x].size() == 1) // x是叶子
            return values[x];
        long long num = 0; // 为子节点最小
        for (int i : g[x])
        {
            if (i != fa)
            {
                num += dfs(i, x, g, values); // 找儿子
            }
        }
        return min((long long)values[x], num); // 选择是不要这个节点还是子节点们
    }

public:
    long long maximumScoreAfterOperations(vector<vector<int>> &edges, vector<int> &values)
    {
        vector<vector<int>> g(values.size());
        g[0].push_back(-1);
        for (auto &e : edges)
        {
            int x = e[0], y = e[1];
            g[x].push_back(y);
            g[y].push_back(x);
        }

        return accumulate(values.begin(), values.end(), 0LL) - dfs(0, -1, g, values);
    }
};